package DoublyLinkedList;

import stack.ListNode;

import java.util.HashMap;
import java.util.Map;

/**
 * P146 LRU缓存
 */
public class P146 {
    public static void main(String[] args) {
        LRUCache lRUCache = new LRUCache(2);
        lRUCache.put(2, 1); // 缓存是 {1=1}
        lRUCache.put(1, 1); // 缓存是 {1=1, 2=2}
//        System.out.println(lRUCache.get(1));;    // 返回 1
        lRUCache.put(2, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
//        System.out.println(lRUCache.get(2));;    // 返回 -1 (未找到)
        lRUCache.put(4, 1); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
        System.out.println(lRUCache.get(1));
        ;    // 返回 -1 (未找到)
        System.out.println(lRUCache.get(2));
        ;    // 返回 3
//        System.out.println(lRUCache.get(4));;    // 返回 4
    }
}

/**
 * 思路：利用双指针的O(1)删除和插入，然后利用哈希表的查找O(1)
 * 将所有操作都变为O(1)
 */
class LRUCache {

//    private class ListNode {
//        int key, value;
//        ListNode pre, next;
//
//        public ListNode(int key, int value) {
//            this.key = key;
//            this.value = value;
//        }
//    }
//
//    //哨兵节点
//    private final ListNode head = new ListNode(0, 0);
//    private final int capacity;
//    private final Map<Integer, ListNode> map = new HashMap<>();
//
//    public LRUCache(int capacity) {
//        this.capacity = capacity;
//        head.pre = head;
//        head.next = head;
//
//    }
//
//    public int get(int key) {
//        ListNode node = getValue(key);
//        return node != null ? node.value : -1;
//    }
//
//    public void put(int key, int value) {
//        ListNode node = getValue(key);
//        if (node != null) {
//            node.value = value;
//            return;
//        }
//
//        // 新书
//        node = new ListNode(key, value);
//        map.put(key, node);
//        insertHead(node);
//
//        if (map.size() > capacity) {
//            ListNode rearNode = head.pre;
//            map.remove(rearNode.key);
//            remove(rearNode);
//        }
//
//
//    }
//
//    //移除节点，将他添加在头
//    private ListNode getValue(int key) {
//        //是否存在,不存在返回空
//        if (!map.containsKey(key)) {
//            return null;
//        }
//        //存在就返回值
//        ListNode node = map.get(key);
//        //覆盖掉
//        remove(node);  //抽出来
//        //放到头
//        insertHead(node);  //排在最开始
//
//        return node;
//    }
//
//    //抽象出删除函数
//    private void remove(ListNode node) {
//
//        node.pre.next = node.next;
//        node.next.pre = node.pre;
//
//    }
//
//    //抽象出查到头节点的方法
//    private void insertHead(ListNode node) {
//        node.pre = head;
//        node.next = head.next;
//        node.pre.next = node;
//        node.next.pre = node;
//    }

    private class ListNode{
        int key,value;
        ListNode pre,next;

        public ListNode() {
        }

        public ListNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private int count;
    private Map<Integer, ListNode> map;
    private ListNode head;
    private int capacity;

    public LRUCache(int capacity) {
        count=0;
        map=new HashMap<>();
        head=new ListNode();
        head.pre=head;
        head.next=head;
        this.capacity=capacity;
    }

    public int get(int key) {
        if(!map.containsKey(key)) return -1;
        // 取出元素
        ListNode listNode = map.get(key);
        // 删除节点
        removeNode(listNode);
        // 添加节点到头部
        addNode(listNode);
        return listNode.value;
    }

    public void put(int key, int value) {
        // 存在，直接取出，然后添加，删除和放到头部
        if(map.containsKey(key)){
            ListNode listNode = map.get(key);
            listNode.value=value;
            removeNode(listNode);
            addNode(listNode);
            return ;
        }

        ListNode node=new ListNode(key,value);
        addNode(node);
        map.put(key,node);
        count++;

        // 空间不够减去尾部
        if(count>=capacity){
            map.remove(head.pre.key);
            removeNode(head.pre);
            count--;
        }
    }

    // 删除节点
    private void removeNode(ListNode node){
        node.pre.next=node.next;
        node.next.pre=node.pre;
    }

    // head是虚节点
    private void addNode(ListNode node){
        node.next=head.next;
        node.pre=head;
        node.next.pre=node;
        node.pre.next=node;
    }

}


